#include "CogGrammar.h"
#include "CogEvolver.h"

// ------------------------------------------------------------------------------------------

CogGrammar::CogGrammar()
: pEvolver(NULL)
{
}

// ----- grammar initialization -----

// return number of errors
size_t CogGrammar::build()
{
	size_t errors = 0;
	startingTemplates.clear();
	errors += rulePool.buildTemplates();
	errors += rulePool.buildInstances();
	rulePool.markConstTemplates();
	rulePool.computeTemplateUsage();
	computeInstanceUsage(); // calculate correct values for validInstances and *Usage
	pEvolver->computeSolutionSize();
	return errors;
}

// ----- production instantiation and mutation -----

CogProduction* CogGrammar::instantiate(CogProduction* startRule, size_t ntSize)
{
	if (startRule->lhs.flag & COGSF_CONST) // terminal productions only need one instance
	{
		// constant; no need to update generation even if usedBy is zero
		startRule->lhs.pRule->use();
		return startRule->lhs.pRule; // pRule of template points to singular instance
	}
	else
	{
		// startRule is first rule to look at
		list<CogProduction*> ruleList;
		ruleList.push_back(startRule);
		// size of existing tree
		size_t ntSizeSoFar = ntSize;
		// for each rule in ruleList...
		for (list<CogProduction*>::iterator rule_iter = ruleList.begin(); rule_iter != ruleList.end(); ++rule_iter)
		{
			if ((*rule_iter)->lhs.flag & COGSF_TEMPLATE) // template only (non-templates added if existing productions selected below)
			{
				// for each RHS of rule...
				for (vector<CogSymbol>::iterator rhs_iter = (*rule_iter)->rhs.begin(); rhs_iter != (*rule_iter)->rhs.end(); ++rhs_iter)
				{
					// ignore terminals
					if (!(rhs_iter->flag & COGSF_TERMINAL))
					{
						// add this production to size
						ntSizeSoFar++;
						CogProduction* pChild;
						// reuse existing production?
						if (((pEvolver->parameters.probReuseOnCreate == 1.0) || (pEvolver->parameters.probReuseOnCreate
							&& (pEvolver->parameters.probReuseOnCreate > cogRandomDouble())))
						    && rhs_iter->pPool->hasInstances())
						{
							pChild = rhs_iter->pPool->getAnyInstance();
						}
						else
						{
							pChild = rhs_iter->pPool->getAnyTemplate();
							if (pChild->lhs.flag & COGSF_CONST) // terminal productions only need one instance
							{
								pChild = pChild->lhs.pRule;
							}
						}
						// add to ruleList
						ruleList.push_back(pChild);
					}
				}
			}
			else // not a template
			{
				ntSizeSoFar += (*rule_iter)->ntSize;
			}
			if (ntSizeSoFar >= pEvolver->parameters.sizeLimit) // oversize!
			{
				return NULL;
			}
		}

		// now process the list in reverse...
		list<CogProduction*>::reverse_iterator rule_iter = ruleList.rbegin();
		list<CogProduction*>::reverse_iterator repl_iter = ruleList.rbegin(); // iterator to replacement element
		for (; rule_iter != ruleList.rend(); ++rule_iter)
		{
			if ((*rule_iter)->lhs.flag & COGSF_TEMPLATE) // template only (non-templates added if existing productions selected above)
			{
				// create a new production
				CogProduction& newrule = (*rule_iter)->lhs.pPool->addNewInstance(pEvolver->getGeneration(), (((*rule_iter)->lhs.flag & COGSF_EVAL) && cache.hasStorage()) ? true : false);
				// resize RHS to size of original production
				newrule.rhs.resize((*rule_iter)->rhs.size());
				// retain everything except starting and template flags
				newrule.lhs.flag = (*rule_iter)->lhs.flag & ~COGSF_STARTING & ~COGSF_TEMPLATE;
				// for each RHS of new/original production...
				for (size_t i = newrule.rhs.size(); i > 0; i--)
				{
					if ((*rule_iter)->rhs[i-1].flag & COGSF_TERMINAL)
					{
						// terminals are copied from original to new
						newrule.rhs[i-1] = (*rule_iter)->rhs[i-1];
					}
					else
					{
						// nonterminals are copied from end of ruleList
						newrule.rhs[i-1] = (*repl_iter)->lhs;
						newrule.ntSize += (*repl_iter)->ntSize;
						(*repl_iter)->use(); // production is USED
						++repl_iter; // "discard" last element of ruleList
					}
				}
				newrule.ntSize++;
				*rule_iter = &newrule; // overwrite list element with pointer to new production
			}
		}
		ruleList.front()->use(); // production is USED
		return ruleList.front(); // return the root production
	}
}

CogProduction* CogGrammar::forceInstantiate(CogProduction* startRule, size_t ntSize)
{
	CogProduction* pRule;
	while (!(pRule = instantiate(startRule, ntSize)))
	{
		// unlimited attempts to fit size limit
	}
	return pRule;
}

CogProduction* CogGrammar::mutate(CogProduction* pRule)
{
	uint32_t startIdx = 0;
	// random index into the size of the solution derived from this rule
	uint32_t targetIdx = cogRandomIndex(pRule->ntSize); // skip starting prod (will fail with solution size 1)
	CogProduction* pAltRule = targetIdx ? mutate(pRule, startIdx, targetIdx, pRule->ntSize) : instantiate(startingTemplates[cogRandomIndex(startingTemplates.size())], 0);
	if (pAltRule && (pRule->lhs.flag & COGSF_STARTING))
	{
		pAltRule->lhs.flag |= COGSF_STARTING; // recover starting flag for root production (all others dropped)
	}
	return pAltRule;
}

CogProduction* CogGrammar::mutate(CogProduction* pRule, uint32_t curIdx, uint32_t targetIdx, size_t ntSize)
{
	CogProduction* pAltRule;
	if (curIdx == targetIdx) // production is to be mutated/replaced
	{
		// replace and instantiate with template
		if (pEvolver->parameters.probDrawFromTemplate && (cogRandomDouble() < pEvolver->parameters.probDrawFromTemplate))
		{
			pAltRule = instantiate(pRule->lhs.pPool->getAnyTemplate(), ntSize - pRule->ntSize);
		}
		else
		{
			// pick an existing production
			pAltRule = pRule->lhs.pPool->getAnyInstance();
			if ((pAltRule == pRule) || (!targetIdx && (pAltRule->lhs.flag & COGSF_STARTING)))
			{
				// picked the original rule? replacing the starting rule with an existing starting rule? instantiate instead!
				pAltRule = instantiate(pRule->lhs.pPool->getAnyTemplate(), ntSize - pRule->ntSize);
			}
			else
			if ((ntSize - pRule->ntSize + pAltRule->ntSize) > pEvolver->parameters.sizeLimit)
			{
				pAltRule = NULL; // exceeded the size limit
			}
			else
			{
				pAltRule->use();
			}
		}
		return pAltRule;
	}
	else // production is not to be mutated/replaced
	{
		// for each RHS of this production...
		for (size_t i = 0; i < pRule->rhs.size(); i++)
		{
			if (!(pRule->rhs[i].flag & COGSF_TERMINAL)) // ignore terminals
			{
				if ((curIdx + pRule->rhs[i].pRule->ntSize) >= targetIdx)
				{
					if (pAltRule = mutate(pRule->rhs[i].pRule, curIdx+1, targetIdx, ntSize))
					{
						// create duplicate of parent of the mutated production...
						CogProduction* pAltParent = &(pRule->lhs.pPool->duplicateInstance(*pRule, pEvolver->getGeneration()));
						// for each RHS of the parent production...
						for (size_t j = 0; j < pAltParent->rhs.size(); j++)
						{
							if (i == j)
							{
								// if RHS element is the mutated one, replace id/pointer to the mutated version
								pAltParent->rhs[j].id = pAltRule->lhs.id;
								pAltParent->rhs[j].flag = pAltRule->lhs.flag & ~COGSF_STARTING; // flag transfer...
								pAltParent->rhs[j].pRule = pAltRule;
							}
							else if (!(pAltParent->rhs[j].flag & COGSF_TERMINAL))
							{
								// show that the production is now used by a new solution
								pAltParent->rhs[j].pRule->use();
							}
						}
						// adjust sizes
						pAltParent->ntSize = pRule->ntSize - pRule->rhs[i].pRule->ntSize + pAltRule->ntSize;
						pAltParent->use(); // parent will be used by its respective parent
						return pAltParent;
					}
					else
					{
						return NULL; // exit because of failed mutation (size limit exceeded?)
					}
				}
				else
				{
					curIdx += pRule->rhs[i].pRule->ntSize;
				}
			}
		}
		return NULL; // exit because target in excess of mutatable productions
	}
}

// ----- production count and removal -----

void CogGrammar::initialize(CogEvolver* _pEvolver)
{
	pEvolver = _pEvolver;
	startingTemplates.clear();
	rulePool.clearAll();
	rulePool.setGrammar(this);
	cache.clear();
	cache.create(&pEvolver->parameters.objectives);
}

void CogGrammar::clearInstancePools()
{
	rulePool.clearInstances();
	rulePool.clearEmptyPools();
	rulePool.clearId();
}

// ----- symbol label management -----

CogProductionPool* CogGrammar::addPool(const string& label, CogProductionPool* pParentPool)
{
	if (pParentPool)
	{
		return &pParentPool->addNewPool(pParentPool->addLabel(label));
	}
	else
	{
		return &rulePool.addNewPool(rulePool.addLabel(label));
	}
}

CogProductionPool* CogGrammar::getPool(const string& label, CogProductionPool* pParentPool)
{
	uint32_t id;
	if (pParentPool)
	{
		if (pParentPool->getId(label, id))
		{
			return pParentPool->getPool(id);
		}
	}
	else
	{
		if (rulePool.getId(label, id))
		{
			return rulePool.getPool(id);
		}
	}
	return NULL;
}

uint32_t CogGrammar::addId(const string& label, CogProductionPool* pParentPool)
{
	if (pParentPool)
	{
		return pParentPool->addLabel(label);
	}
	else
	{
		return rulePool.addLabel(label);
	}
}

uint32_t CogGrammar::getId(const string& label, CogProductionPool* pParentPool)
{
	uint32_t id;
	if (pParentPool)
	{
		pParentPool->getId(label, id);
	}
	else
	{
		rulePool.getId(label, id);
	}
	return id;
}

bool CogGrammar::getTerminalId(const string& label, uint32_t& id) const
{
	bool found = false;
	uint32_t tempId;
	for (size_t i = 0; i < pEvolver->parameters.objectives.stages(); i++)
	{
		for (size_t j = 0; j < pEvolver->parameters.objectives.stageSize(i); j++)
		{
			if (pEvolver->parameters.objectives.objectiveEvaluator(i, j)->getId(label, tempId))
			{
				if (found)
				{
					if (tempId != id)
					{
						return false; // conflict: same name used with different codes by different objective functions - not allowed
					}
				}
				else
				{
					found = true;
				}
				id = tempId;
			}
		}
	}
	return found;
}

bool CogGrammar::getTerminalLabel(uint32_t id, string& label) const
{
	for (size_t i = 0; i < pEvolver->parameters.objectives.stages(); i++)
	{
		for (size_t j = 0; j < pEvolver->parameters.objectives.stageSize(i); j++)
		{
			if (pEvolver->parameters.objectives.objectiveEvaluator(i, j)->getLabel(id, label))
			{
				return true;
			}
		}
	}
	return false;
}

// ----- from/to stream parsing -----

bool CogGrammar::fromStream(istream &in, CogArgumentType addedType)
{
	bool all_success = true;
	while (in.good())
	{
		CogProduction tempRule;
		if (tempRule.fromStream(in, this))
		{
			// add production only if not blank
			if (tempRule.rhs.size() && ((!(tempRule.lhs.flag & COGSF_TEMPLATE) && (addedType & COGARG_OUTPUT_CANDIDATES)) || ((tempRule.lhs.flag & COGSF_TEMPLATE) && (addedType & COGARG_OUTPUT_TEMPLATES))))
			{
				// add the production to the pool
				tempRule.lhs.pPool->addInitialRule(tempRule);
			}
		}
		else
		{
			all_success = false;
		}
	}
	return all_success && !build();
}

void CogGrammar::toStream(ostream &out, CogArgumentType addedType) const
{
	if (addedType & COGARG_OUTPUT_TEMPLATES)
	{
		out << "% -- Template Grammar --" << endl;
		rulePool.templatesToStream(out, this);
	}
	if (addedType & COGARG_OUTPUT_CANDIDATES)
	{
		out << "% -- Candidate Grammar --" << endl;
		rulePool.instancesToStream(out, this);
		#ifdef _DEBUG
		out << "% -- Pool Hierarchy --" << endl;
		rulePool.poolsToStream(out);
		#endif
	}
}

// ------------------------------------------------------------------------------------------